#pragma once
#include "common.h"
// -50000 <= nums[i] <= 50000
void CountSort(vector<int>& nums) {
    int tmp[100001]{};
    int min_val = INT_MAX;
    int max_val = INT_MIN;
    for (int x : nums) {
        tmp[x + 50000]++;
        max_val = max(max_val, x);
        min_val = min(min_val, x);
    }
    int j = 0;
    for (int i = min_val + 50000; i <= max_val + 50000; ++i) {
        while (tmp[i]) {
            nums[j++] = i - 50000;
            --tmp[i];
        }
    }
}